Pada 11 Ogos, 1829, Brigadier Jeneral Charles Gratiot mengarahkan Lee ke Pulau Cockspur, Georgia; bagi melaksanakan rancangan untuk membina kubu di pulau paya yang akan mengawal cawangan Sungai Savannah . Lee yang terlibat pada peringkat awal pembinaan, ketika pulau itu sedang disaliri dan dibina. [25] Pada tahun 1831, ia menjadi jelas bahawa pelan yang sedia ada untuk membina apa yang dikenali sebagai Kubu Pulaski perlu diperbaiki, dan Lee telah dipindahkan ke Kubu Monroe di hujung Semenanjung Virginia (hari ini di Hampton, Virginia ). [26]

Ketika di rumah pada musim panas 1829, Lee kelihatannya telah mendampingi Mary Custis , cicit kepada Martha Washington, yang dia kenali ketika kanak-kanak. Lee mendapat kebenaran untuk menulis surat kepada Mary Custis sebelum pergi ke Georgia, sungguhpun Mary Custis memberi amaran kepada Lee untuk "berhati-hati" dalam tulisannya, kerana ibunya membaca surat-suratnya, terutama dari lelaki. [27] Custis menolak Lee kali pertama beliau melamarnya; bapanya, George Washington Custis tidak percaya anak Kuda RinganHarry Lee merupakan seorang lelaki yang sesuai untuk anak perempuannya. [28] Dia menerima Lee dengan persetujuan ayahnya, pada September 1830, manakala Lee bercuti musim panas, [29] dan kedua-dua mereka telah berkahwin pada 30 Jun 1831, di rumah Custis di Rumah Arlington di bahagian selatan Daerah Columbia (hari ini di Arlington County, Virginia ). [30]

Tugas Lee di Kubu Monroe adalah pelbagai, biasa pada pegawai yang junior, dan termasuk dari belanjawan kepada mereka bentuk bangunan. [31] Sungguhpun Mary Lee mengiringi suaminya ke Jalan Hampton dia menghabiskan kira-kira sepertiga masanya di Arlington, sungguhpun anak pertama pasangan itu, Custis Lee dilahirkan di Kubu Monroe. Sungguhpun menurut semua kisah mereka berdua saling menyayangi, mereka adalah berbeza dari segi perwatakan: Robert Lee adalah kemas dan menepati masa, kualiti yang kurang pada isteri beliau. Mary Lee juga mempunyai masalah peralihan daripada menjadi anak perempuan orang kaya untuk menguruskan isi rumah dengan hanya satu atau dua hamba. [32] Bermula pada tahun 1832, Robert Lee memulakan hubungan platonik tetapi rapat dengan Harriett Talcott, isteri pegawai rakan beliau Andrew Talcott. [33]